package com.PAT.UnSatisfying;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/01/27/14:43
 * @Description: 例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。
 *   前面的属于m，后面属于n，如果如果 n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表
 * @Target: 差9
 */
public class 链表合并 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String head1 = in.next();
        String head2 = in.next();
        int len = in.nextInt();

        LinkNode[] LinkNodes = new LinkNode[len];
        for (int i = 0; i < len; i++) {
            String address = in.next();
            int data  = in.nextInt();
            String next = in.next();
            LinkNode LinkNode = new LinkNode(address,data,next);
            LinkNodes[i] = LinkNode;
        }
        ArrayList<LinkNode> a = null;
        ArrayList<LinkNode> b = null;
        if (dealWithLinkNode(head2, LinkNodes).size()>dealWithLinkNode(head1, LinkNodes).size()){
             a = dealWithLinkNode(head2, LinkNodes);
             b = dealWithLinkNode(head1, LinkNodes);
        }else {
             b = dealWithLinkNode(head2, LinkNodes);
             a = dealWithLinkNode(head1, LinkNodes);
        }

        int blen = b.size()-1;
        for (int count = 1; count <= len; count++) {
            if (count%3==0){

                System.out.print(b.get(b.size()-1).getAddress()+" ");
                System.out.print(b.get(b.size()-1).getData()+" ");
                if (b.size()>1){
                    b.remove(blen--);
                }

                if (count==len){
                    System.out.print("-1");
                }else {
                    System.out.print(a.get(0).getAddress());
                    System.out.println();
                }
            }else if (count%3!=0){
                System.out.print(a.get(0).getAddress()+" ");
                System.out.print(a.get(0).getData()+" ");


                if (count==len){
                    System.out.print("-1");
                }else {
                    if (count%3==2){
                        System.out.print(b.get(b.size()-1).getAddress());
                    }else {  if (a.size()>1){
                        System.out.print(a.get(1).getAddress());}
                    }

                    System.out.println();
                }



                if (a.size()>1){
                    a.remove(0);
                }

            }
        }

    }

    // 此方法用于一个head，然后返回一个排好队的链表
    public static ArrayList<LinkNode> dealWithLinkNode(String head, LinkNode[] LinkNodes){
        String ss = head;
        ArrayList<LinkNode> arrayList = new ArrayList<>();
//        LinkNode[] LinkNodes1 = new LinkNode[LinkNodes.length];
        int index = 0;
        while (!"-1".equals(ss)) {
            for (int i = 0; i < LinkNodes.length; i++) {
                if (LinkNodes[i].getAddress().equals(ss)){
//                    LinkNodes1[index++] = LinkNodes[i];
                    arrayList.add(LinkNodes[i]);
                    ss = LinkNodes[i].getNext();
                }
            }
        }


/*        for (LinkNode linkNode : arrayList) {
            System.out.println(linkNode.toString());
        }*/


        return arrayList;

    }

    static class LinkNode{
        private String Address;
        private int Data;
        private String Next;

        public LinkNode() {
        }

        public LinkNode(String address, int data, String next) {
            Address = address;
            Data = data;
            Next = next;
        }

        @Override
        public String toString() {
            return "LinkNode{" +
                    "Address='" + Address + '\'' +
                    ", Data=" + Data +
                    ", Next='" + Next + '\'' +
                    '}';
        }

        public String getAddress() {
            return Address;
        }

        public void setAddress(String address) {
            Address = address;
        }

        public int getData() {
            return Data;
        }

        public void setData(int data) {
            Data = data;
        }

        public String getNext() {
            return Next;
        }

        public void setNext(String next) {
            Next = next;
        }
    }
}
